#include "calcwhole.hpp"
namespace 运算{
    namespace 整数{
        static char nine_nine[10][10][2]={//0进位 1值
            {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0},{0, 0}},
            {{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7},{0, 8}, {0, 9}},
            {{0, 0}, {0, 2}, {0, 4}, {0, 6}, {0, 8}, {1, 0}, {1, 2},{1, 4}, {1, 6}, {1, 8}},
            {{0, 0}, {0, 3}, {0, 6}, {0, 9}, {1, 2}, {1, 5},{1, 8}, {2, 1}, {2, 4}, {2, 7}},
            {{0, 0}, {0, 4}, {0, 8}, {1, 2}, {1, 6},{2, 0}, {2, 4}, {2, 8}, {3, 2}, {3, 6}},
            {{0, 0}, {0, 5}, {1, 0}, {1, 5},{2, 0}, {2, 5}, {3, 0}, {3, 5}, {4, 0}, {4, 5}},
            {{0, 0}, {0, 6}, {1, 2},{1, 8}, {2, 4}, {3, 0}, {3, 6}, {4, 2}, {4, 8}, {5, 4}},
            {{0, 0}, {0, 7},{1, 4}, {2, 1}, {2, 8}, {3, 5}, {4, 2}, {4, 9}, {5, 6}, {6, 3}},
            {{0, 0}, {0, 8}, {1, 6}, {2, 4}, {3, 2}, {4, 0}, {4, 8}, {5, 6}, {6, 4}, {7, 2}},
            {{0, 0}, {0, 9}, {1, 8}, {2, 7}, {3, 6}, {4, 5}, {5, 4}, {6, 3}, {7, 2}, {8, 1}}
        };
        void 加(const string& a,const string& b,string& out){
            auto asize=a.size(),bsize=b.size();
            if(asize&&bsize){
                const string& es=asize>bsize?b:a,eb=asize>bsize?a:b;
                auto l=es.size();
                out.assign(eb.size()+1,0);
                auto set=out.begin();
                auto as=a.begin(),bs=b.begin();
                while(l--){
                    int temp=*as++ +*bs++,res=temp-10;
                    if(res<0){*set++=temp;continue;}//没进位
                    *(set+1)++;
                    *set++=res;
                }
                as=eb.begin()+es.size(),bs=eb.end();
                while(as<bs){
                    int temp=*as++,res=temp-10;
                    if(res<0){*set++=temp;continue;}
                    *(set+1)++;
                    *set++=res;
                }
                if(!out.back()&&out.size()>1)out.pop_back();
                return;
            }
            if(!asize){
                out=b;
                return;
            }
            if(!bsize){
                out=a;
                return;
            }
            out.assign(1,0);
        }
        int 减(string::const_iterator abegin,string::const_iterator aend,
        string::const_iterator bbegin,string::const_iterator bend,
        string& out){
            auto asize=aend-abegin,bsize=bend-bbegin;
            if(asize&&bsize){
                int ret=asize<bsize?-1:1;
                string::const_iterator esb,ese,ebb,ebe;
                if(asize<bsize){
                    esb=abegin,ese=aend;
                    ebb=bbegin,ebe=bend;
                }
                else{
                    esb=bbegin,ese=bend;
                    ebb=abegin,ebe=aend;
                }
                auto l=ese-esb;
                out.assign(ebe-ebb,0);
                int carry=0;
                auto set=out.begin();
                auto x=ebb,y=esb,xe=ebe;
                if(asize==bsize){
                    if(*(aend-1)<*(bend-1))ret=-1,x=bbegin,y=abegin,xe=bend;
                    else ret=1,x=abegin,y=bbegin,xe=aend;
                }
                auto as=x,bs=y;
                while(l--){
                    int temp=*as++ -*bs++ -carry;
                    if(temp>=0){*set++=temp,carry=0;continue;}//没退位
                    *set++=temp+10,carry=1;
                }
                as=x+(ese-esb),bs=xe;
                if(carry){
                    if(asize==bsize){
                        if(out.back()==9)out.pop_back();//-1+10
                        return -1;
                    }
                    while(as<bs){
                        int temp=*as++-carry;
                        if(temp>=0){*set++=temp,carry=0;continue;}//没退位
                        *set++=temp+10,carry=1;
                    }
                    while(!out.back()&&out.size()>1)out.pop_back();
                    if(carry)return -1;
                    return ret;
                }
                while(as<bs)*set++=*as++;
                while(!out.back()&&out.size()>1)out.pop_back();
                return ret;
            }
            if(!asize){
                out.assign(bbegin,bend);
                return -1;
            }
            if(!bsize){
                out.assign(abegin,aend);
                return 1;
            }
            out.assign(1,0);
            return 1;
        }
        int 减(const string& a,const string& b,string& out){
            return 减(a.begin(),a.end(),b.begin(),b.end(),out);
        }
        void 乘(const string& a,const string& b,string& out){
            /*采用一次性错位逐加法，例如123x321：
                123
                321
                ---
            0123 偏移=0
            +0246 偏移=1
            +0369 偏移=2
            ------
            039483
            */
            auto bsize=b.size(),asize=a.size();
            if(!asize||!bsize){out.assign(1,0);return;}
            out.assign(asize+bsize,0);
            auto data=(char*)out.data();
            for(size_t i=0;i<bsize;i++){
                if(b[i]){
                    char carry=0;
                    for(size_t j=0;j<asize;j++){
                        size_t ij=i+j;
                        auto nn=nine_nine[b[i]][a[j]];
                        data[ij]+=nn[1]+carry;
                        carry=nn[0];
                        auto rest=data[ij]-10;
                        if(rest>=0)carry++,data[ij]=rest;
                    }
                    data[i+asize]=carry;
                }
            }
            while(!out.back()&&out.size()>1)out.pop_back();
        }
        /*
        void Print(string::iterator begin,string::iterator end){
            begin--;
            end--;
            for(;begin!=end;end--)printf("%d",*end);
        }
        void Print(string::const_iterator begin,string::const_iterator end){
            begin--;
            end--;
            for(;begin!=end;end--)printf("%d",*end);
        }*/
        int 比较(const string& a,const string& b){
            auto asize=a.size(),bsize=b.size();
            if(asize>bsize)return 1;
            if(asize<bsize)return -1;
            auto as=a.rbegin(),bs=b.rbegin();
            while(asize--){
                auto v=*as++-*bs++;
                if(v<0)return -1;
                if(v>0)return 1;
            }
            return 0;
        }
        void 除(const string& a,const string& b,string& whole,string& small,size_t n){
            //整数小数部分分开算
            string remain,k;
            整除(a,b,whole,remain);
            string temp(remain.size()+n,0);
            small.assign(n,0);
            copy(remain.begin(),remain.end(),temp.begin()+n);
            auto abegin=temp.begin()+n-1,aend=abegin+remain.size()+1;
            auto bbegin=b.begin(),bend=b.end();
            auto sbegin=small.rbegin();
            for(size_t i=0;i<n;i++){
                整除(abegin,aend,bbegin,bend,k,remain);
                *sbegin++=k.front();
                copy(remain.begin(),remain.end(),abegin);
                aend-=aend-abegin-remain.size();
                abegin--;
            }
        }
        void 整除(string::const_iterator abegin,string::const_iterator aend,
        string::const_iterator bbegin,const string::const_iterator bend,
        string& result,string& remain){
            /*采用字符串拷贝法
            如 156/13=12
                21
            31√651->0
               62 ->1
                31->2
            */
            auto asize=aend-abegin,bsize=bend-bbegin;
            if(!bsize)throw 除0();
            if(!*(bend-1))throw 除0();
            if(!asize){
                result.assign(1,0);
                remain.assign(1,0);
                return;
            }
            remain.assign(abegin,aend);
            if(bsize>asize){//明显不能算
                result.assign(1,0);
                return;
            }
            result.assign(asize-bsize+1,0);
            auto cur=remain.end()-bsize,begin=remain.begin()-1,end=cur+bsize;
            auto set=result.rbegin();
            string temp;
            while(cur!=begin){
                char count=0;
                while(减(cur,end,bbegin,bend,temp)==1){
                    count++;
                    copy(temp.begin(),temp.end(),cur);
                    fill(cur+temp.size(),end,0);
                }
                *set++=count;
                while(end!=cur){
                    if(*(end-1))break;
                    end--;
                }
                cur--;
            }
            while(!remain.back()&&remain.size()>1)remain.pop_back();
            while(!result.back()&&result.size()>1)result.pop_back();
        }
        void 整除(const string& a,const string& b,string& result,string& remain){
            整除(a.begin(),a.end(),b.begin(),b.end(),result,remain);
        }
    }
}